Reversible Causal Graph Dynamics

摘要

Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree,time-varying graphs. The whole graph evolves in discrete time steps, and thisglobal evolution is required to have a number of physics-like symmetries:shift-invariance (it acts everywhere the same) and causality (information has abounded speed of propagation). We add a further physics-like symmetry, namelyreversibility. KEYWORDS: Bijective, invertible, injective, surjective,one-to-one, onto, Cayley graphs, Hedlund, Block representation, Lattice-gasautomaton, Reversible Cellular Automata.